
\section{Three-move lag}
\label{Strategy3Lag}
In the three-move lag problem the bomb takes three time units to explode. 
The target nodes for the bomber are different than in the two-move lag, because after three steps the ship can be one or three units distance in front or behind. 
So for the one-restricted graph on figure \ref{GraphN2} the ship, currently at node \textit{0}, can be at the nodes \textit{3,1,-1} or \textit{-3} after three steps. 

\subsection{Equalizing the probabilities}
\label{Equalizing}
In order to find the best strategy for the ship, the following reasoning is used. If at each instant the probability of the ship being in every possible place is equal, then this would be maximizing the chances for the ship to evade the bomb. Or in other words, this would be an optimal strategy.
To be certain about this idea, first it is tested for the two-move lag problem on a one-restricted graph. 
This means that the ship could only move on a line to the right or to the left. The figure \ref{GuilhermePicture} below shows the idea. 
The vertical axis represents the time, the vertical axis represent the possible places the ship can be at each time. \\

\begin{figure}[h]
 \includegraphics[width=3.2in]{Bilder/GuilhermePicture}
\caption{two-move}
\label{GuilhermePicture}
\end{figure}

Suppose the ship starts its movement in $S_0$. After the first two movements, it may be at one of three places $S_1$, $S_3$ or $S_2$, where $S_2$ is equal to $S_0$, as shown on the figure. \\
The probability of being in each of these places is given by:
\begin{equation} S_1=p_5*p_1 \end{equation}
\begin{equation} S_2=p_5*p_2+p_6*p_3 \end{equation}
\begin{equation} S_3=p_6*p_4 \end{equation}



As already explained, the idea is to divide the probability of the ship being there equally among these three places. To this end, the following function was created: 
\begin{equation}
\begin{aligned}
 f(p_1,p_2,p_3,p_4,p_5,p_6)=abs(p_5*p_1-1/3)\\+abs(p_5*p_2+p_6*p_3-1/3)+abs(p_6*p_4-1/3)
\end{aligned}
\end{equation}


Using Matlab optimization tools, the goal was to find the six probabilities which minimize the function $f$.


It is necessary to recalculate the function $f$ at each movement of the ship, but taking into account that the probabilities $p_5$ and $p_6$ will already be set. To better understand what is happening, imagine that the ship is moving initially to the right. After that, it can move to the left with probability $p_3$ or to the right with probability $p_4$. At this point, the probabilities which minimize the function $f$ must be found. However, the values $p_5$ and $p_6$ will be respectively the old $p_3$ and $p_4$ values, and they will be labelled $p_5^*$ and $p_6^*$, to remember they are not variables any more. \\
Thus, from the second movement forward, the function reduces to: 
\begin{equation}
\begin{aligned}
f(p_1,p_2,p_3,p_4)=abs(p_5^**p_1-1/3)\\
+abs(p_5^**p_2+p_6^**p_3-1/3)+abs(p_6^**p_4-1/3)
\end{aligned}
\end{equation}


The values of $p_5^*$ and $p_6^*$ are already known, so, knowing the probabilities of one movement behind, it is necessary to find the values that minimize the function for the current movement, as a Markov process. \\
By repeating this process, satisfactory values were found, and thus the probabilities $S_1$, $S_2$ and $S_3$ were calculated. The values are all less than $0.382$, which concurs with the results presented by Ferguson as being the value of the game. \\
Having found a satisfactory result for the two-move lag problem, the same idea was applied to the three-move lag problem. The algorithm used is analogous with only two differences. The first is that the number of variables is bigger because the ship can make one more movement, the second is that except for the first movement, the new probabilities calculated take into account not only the values found from one previous movement, but from two previous movements. \\
Using Matlab optimization tools, no set of values satisfying the problem constrains was found. Given so, the solution for the three-move lag was not found.

So, in short, it was proved that there is an optimal Markov strategy for the ship for the two-move lag problem, and that there is no such strategy for the three-move lag problem.


\subsection{Strategies for the ship}
For the ship three strategies are explored: 
Firstly, in section \ref{StrategyFerguson3Lag} a strategy by Ferguson is investigated, 
then in section \ref{twoDependent} a two-dependent strategy is described, and finally section \ref{StrategyLeeLee} shows 
a strategy invented by Lee and Lee \cite{Isaacs}.
\subsubsection{Strategy Ferguson}
\label{StrategyFerguson3Lag}
The first possible strategy the ship can use is the strategy described in section \ref{Strategy2Lag}, which says that the ship moves forwards with probability $p$ and backwards with probability $1-np$. 
The following equations show with what probabilities the ship will be at any of the possible places after three steps if it is using this strategy:
\begin{itemize}
\item Probability to be at any of the $n^3$ points three steps in front, not passing the node just visited $P(N_3)=p^3$
 \item Probability to be at any of the $n$ points one step in front, not passing the node just visited $P(N_1)= np^2(1-np)+2(1-np)^2p+(n-1)p^2(1-np)$
\item Probability to be at the point one step behind, passing the node just visited $P(N_{-1})=(1-np)^3+(1-np)^2np+n(1-np)p^2$
\item Probability to be at any of the $n^2$ points three steps behind, passing the node just visited $P(N_{-3})=p^2(1-np)$
\end{itemize}
In figure \ref{plottedDiagramm} the four equations are plotted for $n=1$. The minimum of the maximum is found at $p=\frac{2}{3}$ and than 
the resulting value is $v_1=\frac{8}{27}$. For $n=1,2,3,4$ the minimum of the maximum is always found at the intersection of $P(N_3)$ and $P(N_1)$. 
Table \ref{table3lagF} shows the optimal p's and the resulting values for $n=1,2,3,4$ for the three-move lag by using the same strategy as in the two-move lag. 
\begin{figure}[h]
 \includegraphics[width=3.2in]{Bilder/3LagN2Diagramm}
\caption{$P(N_3), P(N_1), P(N_{-1}), P(N_{-3})$ for $n=1$}
\label{plottedDiagramm}
\end{figure}

\begin{table}[h]
\begin{center}
 \resizebox{8cm}{!}{
 \begin{tabular}{|c|c|c|}
  \hline  
  n&p&v	\\
  \hline
  1 & $\frac{2}{3} \approx 0.6667$ & $\frac{8}{27} \approx 0.2963$ \\
  \hline 
  2& $\frac{5}{2}-\frac{1}{2}\sqrt{17} \approx 0.4385 $ & $ \frac{95}{2}-\frac{23}{2}\sqrt{17} \approx 0.0843 $\\
  \hline 
  3& $\frac{7}{4}-\frac{1}{4}\sqrt{33} \approx 0.3139$ & $ \frac{259}{16}-\frac{45}{16}\sqrt{33} \approx 0.0309$\\
  \hline 
  4& $\frac{3}{2}-\frac{1}{6}\sqrt{57} \approx 0.2417$ & $ \frac{21}{2}-\frac{25}{18}\sqrt{57} \approx 0.0141$\\
\hline
 \end{tabular}}
\caption{Ship Ferguson for three-move lag: optimal p and values}
\label{table3lagF}
\end{center}
\end{table}

\subsubsection{Two-dependent strategy}
\label{twoDependent}
If the ship is using Ferguson's strategy for the three-move lag, it is the best for it to move with the probabilities shown in table \ref{table3lagF}, because then the probability to be hit is the lowest. But the 
strategy to move forwards with probability $p$ and backwards with probability $1-np$ is not optimal for the three-move lag. 
The following counterexample for $n=1$ shows that if the ship uses a two-dependent strategy, 
it obtains a better value. Hence Ferguson's strategy is not optimal for the three-lag problem.

In a two-dependent strategy the ship's next move depends on its last two moves. So if the ship moved two times in the same direction ($\rightarrow \rightarrow$), the next 
step will also go in this direction with probability $p_0$ and in the opposite direction with probability ($1-p_0$). But if the last two moves were in opposite directions ($\rightarrow \leftarrow$) 
the ship moves in the same direction like the previous move with probability $p_1$ and in the opposite direction with probability ($1-p_1$). \cite{Ferguson}
If this strategy is applied for the three-move lag and $n=1$ there are the following probabilities where the ship will be after three steps: 
\begin{itemize}
 \item $P(N_3/ \rightarrow \rightarrow) = {p_0}^3$
 \item $P(N_1/ \rightarrow \rightarrow) = {p_0}^2(1-p_0)+ p_0(1-p_0)(1-p_1)+(1-p_0)(1-p_1)p_1$
\item $P(N_{-1} / \rightarrow \rightarrow) = (1-p_0)(1-p_1)^2+ (1-p_0)^2p_1+p_0(1-p_0)p_1$
\item $P(N_{-3} / \rightarrow \rightarrow) = (1-p_0)p_1p_0$
\item $P(N_3/ \rightarrow \leftarrow) = p_1p_0^2$
\item $P(N_1/ \rightarrow \leftarrow) = p_1p_0(1-p_0)+ p_1(1-p_0)(1-p_1)+(1-p_1)^2p_1$
\item $P(N_{-1}/ \rightarrow \leftarrow) = (1-p_1)^3+(1-p_1)p_1(1-p_0)+p_1^2(1-p_0)$
\item $P(N_{-3}/ \rightarrow \leftarrow) = (1-p_1)p_1p_0$
\end{itemize}
For $p_0=\frac{3-\sqrt{3}}{2}$ and $p_1=\sqrt{3}-1$ the maximum value is $P(N_{-3}/ \rightarrow \rightarrow) = P(N_1/\rightarrow \leftarrow) =\frac{3(3\sqrt{3}-5)}{2} \approx 0.294229$ which is 
smaller than $\frac{8}{27}$, the value the ship can reach by using Ferguson's strategy.  \cite{Ferguson}

With this counterexample it is shown that for the ship, the optimal strategy for the two-move lag is not optimal for the three-move lag.

\subsubsection{Strategy Lee Lee} 
\label{StrategyLeeLee}
But also the value resulting from the two-dependent strategy can still be improved. The strategy described by Lee and Lee \cite{Isaacs} reduces the upper bound of the value for a one restricted graph $v_1$ to 0.2883686. The idea 
is to reduce the upper bound by counting the number of tails (ship moves in the opposite direction as the previous step) followed by the number of straights (ship moves in the same direction as the previous move) 
and to go forwards with a certain probability with respect to that. \\
At most there are counted \textit{$t_{max}$} tails and \textit{$s_{max}$} straights. \\
The state of the path $S_p = (i,j)$ counts the number of tails followed by the number of straights: 
\[i = \left\{
 \begin{array}{cc}
 \#tails &, \#tails < t_{max}\\
t_{max} &, otherwise
 \end{array} \right. \]
\[j = \left\{
 \begin{array}{cc}
 \#straights+1 &, \#straights+1 < s_{max}\\
s_{max} &, otherwise
 \end{array} \right. \]
So for example if the ship in the one-restricted graph from figure \ref{GraphN2} goes from node \textit{1} to node \textit{0} and then follows the path \textit{0 1 0 -1 -2},  $S_p= (2,3)$. 
In the strategy \textit{LeeLee} the ship moves forwards with 
probability $x_{ij}$ and backwards with probability $(1-x_{ij})$ if $S_p=(i,j)$, which is the reason why there are $t_{max}*s_{max}$ different probabilities to move forwards. 

The function $g_{ijk}$ defines the probability to be at place $k$ ($k=1,2,3,4$) after three time units under the condition that $S_p=(i,j)$; it defines the probability to be one in front, three in front, one behind or three behind 
after three steps, depending on the number of tails followed by straights in the past. For example the probability to be three steps in front $g_{ij1}=x_{ij}x_{ij+1}x_{ij+2}$. 
The aim is to find the values for all $x_{ij}$ such that the maximum of $g_{ijk}$ for $i=1\dots t_{max}$, $j=1\dots s_{max}$ and $k=1,2,3,4$ is minimized.  

For $t_{max}=10$ and $s_{max}=40$ the upper value $v$ can be reduced to 
$v_{LeeLee}\approx 0.288369 $, which is less than $v_{Ferguson}\approx 0.296296$, the reachable value by using Ferguson's strategy for three-move lag. And also the value 
resulting from the two-depending strategy $v_{two-dependent}\approx 0.294229$ is undercut. 
By observing more than $t_{max}=10$ tails or $s_{max}=40$ straights in the past, the values cannot be improved significantly. \cite{Isaacs}

\subsection{Strategies for the bomber }
First, section \ref{SFB3Lag} shows why the strategy for the bomber described in \ref{Strategy2LagBomber} cannot be applied to 
the three-move lag. A new strategy that can be applied to the three-move lag problem is explained in section \ref{ObservingBomber}.
\subsubsection{Strategy Ferguson}
\label{SFB3Lag}
In the three-move lag, the bomber's strategy from chapter \ref{Strategy2LagBomber}, which always conditions on the ship's last move, cannot be applied. 
This section clarifies the difference between 
the two-move and three-move lag for the bomber and why another strategy has to be found. 

\begin{figure}[h]
\begin{center}
 \includegraphics[width=2.5in]{Bilder/FergusonBomber3Lag}
\caption{Bombers strategy for 1-restricted graph, three-move lag}
\label{GraphBomber3Lag}
\end{center}
\end{figure}

Figure \ref{GraphBomber3Lag} shows the application of Ferguson's strategy from section \ref{Strategy2LagBomber} for the three move lag. The ship is at node \textit{0}, and since it can be at the 
nodes \textit{-1} and \textit{1} after three steps, the bomber bombs these places with probability $p_0$. 
Then the ship moves from node \textit{0} to node \textit{1} and the bomber drops the bomb on node \textit{2} or node \textit{4} with probability $p_1$.  
But now the difference to the two-move lag problem occurs. 
Under the condition that it does not return to the starting node \textit{0}, 
but moves to node \textit{2}, there are two different probabilities to hit the ship, depending on it's next move: 
\[w = \left\{
 \begin{array}{cc}
 \frac{p_1}{2p_0+2p_1} &\text{, if the ship does not return to node 1}\\
 \frac{p_0}{2p_0+2p_1}&\text{, if the ship returns to node 1}
 \end{array} \right. \]
So it is not enough to only condition on the ship's next move and therefore another bomber strategy is necessary for the 
three-move lag; the observing bomber.

\subsubsection{Observing Bomber}
\label{ObservingBomber}
A bomber strategy which is able to play against different types of ships in different 
types of graphs is the observing bomber strategy. 
This strategy first observes some steps of the ship. 
Observing means that the bomber counts the number of times the ship is going forward, staying still and going backward. 
After observing a certain number of steps the bomber calculates the probabilities for these three possible moves of the ship. For instance $p_{forwards} = \frac{\#_{forwards}}{\#_{observed}}$. 
Then these three probabilities are used to create probabilities for all possible bombing places. After that the places will be bombed with the calculated probabilities. 

\begin{figure}[h]
\begin{center}
 \includegraphics[width=3.3in]{Bilder/2restrictedGraphObservingBomber}
\caption{Example: Observing Bomber for two-restricted graph}
\label{ExampleObservingBomber}
\end{center}
\end{figure}

Figure \ref{ExampleObservingBomber} shows an example of the calculation of the observing bomber. This example shows a situation for the two-move lag problem with $n=1$. \\
The ship is based on the Ferguson algorithm and is not allowed to stay. The actual position of the ship is node \textit{0} 
and it came from node \textit{-1} before.\\
The bomber calculates the following probabilities of the three different types of moving/staying by observing the ship:
\begin{itemize}
\item pForward = 0.626
\item pStay = 0
\item pBack = 0.374
\end{itemize}


These three probabilities are used to create probabilities for all different bombing places, which are all possible positions of the ship after the next two steps. \\
Figure \ref{ExampleObservingBomber} shows these probabilities and the moves the ship has to take to get there. As you can see there are three different places possible. \\
The first one is node \textit{2} which is reached by the ship if it goes forwards two times. The second one is node \textit{0} which is the actual position of the ship. The ship is there again after two moves if it first goes forwards and then backwards or if it goes backwards two times. 
The probabilities of these two moves are added up to get the probability for bombing place \textit{0}. 
The third possible position is node \textit{-2}. This is reached if the ship first goes backwards and then forwards. 

